The present invention relates to a system, a device and a method of providing secure communication between two parties, and in particular for providing such secure communication over a communication network.
Secure communication between two parties has always been an important but difficult task. The moment information is shared between two parties, a third, unauthorized party may be able to access this information as well. The problem is magnified when the two authorized parties are separated by a distance, so that information must be passed in the form of messages rather than by direct communication. Historically, the content of messages has sometimes been protected by cryptography, in which the content is altered by transformation into another form which is understandable only by the intended recipient or recipients of the message.
As the technology for transferring information has become increasingly complex and sophisticated, so has the technology of cryptography. Currently, cryptography may be performed by encoding the original message into an incomprehensible protected message according to mathematical algorithms using a particular key. Only the correct recipient should have both the same algorithm and the particular key needed to decode the protected message into the original message. Thus, the incomprehensible encoded message can be freely transmitted over a relatively insecure communication channel such as a telephone network, while remaining secure to all but the correct recipient.
Of course, the security of the encoded message depends both upon the possession of the key and the ability of the algorithm to resist being broken by an unauthorized third party. A third party could try to guess the identity of the key, in effect copying it, and then use the actual key to decode the message. Also, just as a door may be broken without having the key to the lock, so can a cryptography algorithm be broken in the absence of the correct mathematical key. In both cases, the longer the key, the more difficult either guessing attacks or brute force attacks become.
However, as computer technology has become ever faster, many heretofore xe2x80x9cimpregnablexe2x80x9d algorithms have yielded to brute force attacks. For example, the DES (Data Encryption Standard) algorithm with a 56-bit key was thought to be impregnable at the time of its inception in 1976. By 1993, DES with the 56-bit key could theoretically have been broken in 7 hours by brute force with a highly sophisticated computer. To solve the problem, the key was lengthened to 128 bits. Other algorithms have proven to be susceptible to brute force attacks, and are now used with longer keys to reduce their vulnerability to attacks.
Since computer technology is still becoming increasingly powerful and faster, there is no reason to expect that the xe2x80x9cimpregnablexe2x80x9d algorithms of today will not fall to a brute force attack tomorrow. Furthermore, certain algorithms have become easier to crack by the discovery of new mathematical functions, such as new factoring algorithms, which cannot be easily anticipated. Such functions can render xe2x80x9csecurexe2x80x9d cryptography algorithms vulnerable to attack. Thus, expecting mathematical algorithms alone to provide all of the security for information transfer is clearly not sufficient.
An additional layer of security is provided by using public key-private key pairs. In this system, used for example in the PGP (Pretty Good Privacy) cryptography software, the sender encrypts the message using the public key, and the recipient decrypts it with the private key.
As noted previously, such security measures through cryptography are important for sending secure messages over insecure communication channels. For example, voice and facsimile transmissions are typically sent over telephone networks, which can be tapped. The problem is magnified for such highly insecure communication channels as cellular phones, which are easy to access with hardware, such as a scanner, which can be purchased xe2x80x9coff the shelfxe2x80x9d at an electronics store. Thus, devices and methods for securing communication on insecure channels are important.
One example of such a method is disclosed in U.S. Pat. No. 5,473,689 to Eberhard. In this method, two electronic devices generate and exchange two random numbers, so that each device knows both numbers. Both numbers are then encrypted and compared, by exchanging a portion of each encrypted number. Communication only occurs if both encrypted numbers match. One problem with this method is that both sides must have the same key for the encryption and decryption of the random numbers. Thus, this key is vulnerable to theft by an unauthorized party, particularly if the key is exchanged.
U.S. Pat. No. 5,564,106 to Puhl et al. describes a method of providing blind access to an encryption key, such that the key of a first group member is provided to a second group without the first group knowing the identity of the first group member. Such a method is useful for enabling a government organization which is investigating an employee of a business to access the key of that employee, without enabling the business to know the identity of the employee under investigation. However, this method is not helpful for secure communication over an insecure channel, since it presupposes the security of the original encryption method.
One drawback of some currently available encryption methods for communication over an insecure channel is that they require the user to perform a number of steps before communication occurs. If such encryption were to be performed automatically, for example by a semiconductor chip contained with a communication device, the user would not need to actively perform the encryption before communication would occur. One example of such a device is disclosed in U.S. Pat. No. 5,539,828 to Davis. This device has both a pair of keys, public and private, and a digital certificate which includes the public key encrypted with the private key. Essentially, this device has automated public key encryption, so that again communication through the device is only as secure as the encryption method.
Other commercially available hardware devices, or hardware/software systems, suffer from the same potential drawback: the devices and systems are only as secure as the encryption method which is employed. Examples of such devices and systems include the information security products of Litronic (Costa Mesa, Calif., USA), which include both smartcard readers and cryptographic device drivers, and software for encrypting textual and database information; the network security products of Cylink Corp. (San Francisco, Calif., USA), which help ensure security on LAN (Local Area Networks) and WAN (Wide Area Networks), through the use of the DES encryption algorithm; and the products of Cylink (Sunnyvale, Calif., USA), which provide rapid encryption for digital networks, again using either DES or a proprietary encryption algorithm. These are only a sampling of the many such products available on the market today, indicating the wide-spread popularity of, and commercial need for, products for secure communication and encryption.
Unfortunately, as noted previously, all of these products are only as secure as the encryption method employed. Furthermore, all of the encryption methods employed are based upon mathematical algorithms and keys, which means that they can potentially be cracked by a brute force attack. As computer technology becomes more sophisticated and as new mathematical functions related to these algorithms become available, such brute force attacks become easier to manage, thereby rendering the encrypted data vulnerable to unauthorized interception.
There is one type of encryption, however, which is theoretically unbreakable by a brute force attack on the encrypted message itself. This type of encryption involves random numbers which are as long as the message itself. There is no potentially breakable algorithm. Rather, the message is encoded according to a random number of the same length as the message. The encoded message can then only be decoded by using exactly the same random number as was used for the encoding. Each such random number is used only once for encoding a message. Since random numbers are used for the encoding, the random number used for the encoding cannot be guessed or derived according to a mathematical algorithm, or according to statistical analysis. In order to obtain the random number by guessing, the entire random number used for encoding a particular message must be guessed, which is effectively guessing the message itself. Furthermore, obtaining one such random number by reverse-engineering will not enable other messages to be decoded, since subsequent messages will be encoded with different random numbers.
Currently, this encryption method requires both parties to have the same random number, typically by using a one-time pad of such numbers. This pad can be literally a physical pad of paper, on which a series of random numbers is written. The pad could also be in the form of an electronic storage hardware device such as a diskette. As a message is sent or received, each party uses one number on the pad, and then discards the random number. Since both parties have the same pad and are using the same random numbers, messages can be securely encoded and decoded, without fear of a brute force attack. Of course, the pad of paper or the diskette itself could be physically stolen or copied, but such an occurrence is relatively easier to guard against and to detect than electronic theft of the messages.
One severe drawback of the xe2x80x9cone-time padxe2x80x9d in currently available implementations is that both parties must have the same physical pad of paper or diskette before communication can occur, thereby restricting communication to parties which have made the necessary arrangements in advance. Also, the protection of the messages is only as good as the physical protection of the one-time pad itself on both sides. Furthermore, both parties must take certain steps in order for the encoding and decoding steps to occur. In addition, the physical pad of paper or computer diskette cannot hold an infinite quantity of these random numbers, so that the physical pad of paper or the computer diskette must be periodically replaced. Thus, as currently available, the method is both cumbersome and not practicable for wide-spread communication between many different parties.
There is therefore a need for, and it would be useful to have, a method and a system for producing and using an electronic xe2x80x9cone-time padxe2x80x9d, for example for secure communication on an insecure channel or for secure identification, which is automated and practicable for wide-spread communication and other uses, yet which is not liable to a brute force attack on the xe2x80x9cone-time padxe2x80x9d itself.
According to the present invention, there is provided a method for generating an identical electronic one-time pad at a first location and at a second location, the method comprising the steps of: (a) providing a first electronic device at the first location and a second electronic device at the second location, each of the first and the second electronic devices having: (i) a non-volatile memory; (ii) a processor; (iii) at least one table of true random numbers being stored on the non-volatile memory, the table being identical for the first and the second electronic devices; and (iv) at least one software program for obtaining a true random number from the table, the software program being stored on the non-volatile memory and the at least one software program being operated by the processor; (b) providing a communication channel for communication between the first electronic device and the second electronic device; and (c) selecting a selected true random number from the table at the first and the second electronic devices according to a selection procedure, the selection procedure being identical for the first and the second electronic devices, the selection procedure including exchanging at least a portion of a key between the first and the second electronic devices over the communication channel, such that the selected true random number is identical for the first and the second electronic devices; and (d) forming at least a portion of the identical electronic one-time pad at the first and the second locations with the selected true random number.
Preferably the identical electronic one-time pad is of any desired length.
According to preferred embodiments of the present invention, the step of selecting the selected true random number from the table includes the steps of: (i) generating a first true random number at the first electronic device and a second true random number at the second electronic device; and (ii) sending the first true random number to the second electronic device and the second true random number to the first electronic device through the channel, the first and the second true random numbers forming the at least a portion of the key. Preferably, the method further comprises the step of: (iii) obtaining an obtained true random number from the table with a pointer, the pointer being substantially identical to the key, such that the selected true random number is selected according to the obtained true random number. More preferably, the selected true random number is the obtained true random number.
Alternatively and more preferably, the method further comprises the step of: (ii-a) merging the first and the second true random numbers to form the at least a portion of the key.
According to other preferred embodiments of the present invention, at least one of the first and the second electronic devices includes a source of physical random phenomena, such that at least one of the first and the second true random numbers is generated from the source of physical random phenomena. Preferably, the source of physical random phenomena is selected from the group consisting of a source of acoustic noise and a source of thermal noise.
According to other preferred embodiments of the present invention, at least one of the first and the second electronic devices features a pseudorandom number generator being operated by the processor according to at least one software program being stored in the non-volatile memory, the pseudorandom number generator being operated substantially continuously for an undefined period of time, the step of generating at least one of the first and the second true random numbers including the step of outputting an output number from the pseudorandom number generator.
Preferably, the method further comprises the steps of: (iv) providing at least one identical pseudorandom number generator at the first and the second electronic devices, the at least one pseudorandom number generator being operated by the processor according to at least one software program being stored in the non-volatile memory; (v) obtaining an obtained true random number from the table with a first pointer, the first pointer being substantially identical to the key; (vi) giving the obtained true random number to the at least one pseudorandom number generator as a seed; (vii) obtaining a generated pseudorandom number from the at least one pseudorandom number generator, the generated pseudorandom number being identical for the first and the second electronic devices; and (viii) selecting the selected true random number from the table by using the generated pseudorandom number as a second pointer. More preferably, the step of selecting the selected true random number further comprises the steps of: (1) generating a second generated pseudorandom number from the at least one pseudorandom number generator, the second generated pseudorandom number being identical for the first and the second electronic devices; and (2) merging the second generated pseudorandom number with the selected true random number to form a merged true random number, the merged true random number being the selected true random number. Most preferably, the method further comprises the step of repeating the steps (vi)-(viii) and (1) and (2) at least once, wherein the selected true random number is the obtained true random number for step (vi) and the second pointer is the selected true random number from step (2) for repeating these steps. Preferably, a plurality of selected true random numbers is obtained by repeating this process at least once.
According to still other preferred embodiments of the present invention, the method further comprises the steps of: (d) encrypting a message by the first electronic device according to the one-time pad to form an encrypted message by merging at least a portion of the message with the selected true random number from the one-time pad according to an invertible merging function; and (e) sending the encrypted message to the second electronic device through the communication channel.
Preferably, the method further comprises the steps of: (f) receiving the encrypted message by the second electronic device; and (g) decrypting the encrypted message by performing the inverse function on the encrypted message to obtain the at least a portion of the message.
Preferably, the message is divisible into a plurality of portions. More preferably, the message is divisible into a plurality of bytes, and the at least a portion of the message is one of the plurality of bytes. Most preferably, the merging function includes the step of performing XOR operation with the selected true random number and the byte of the message.
Also preferably, the plurality of true random numbers is generated by changing the seed of a pseudorandom number generator at random times. The seed can be changed by replacing or modifying it with selected random numbers. The random times themselves can also be selected according to random numbers.
According to yet another preferred embodiment of the present invention, the method further comprises the steps of: (d) encrypting an identifier by the first electronic device according to the one-time pad to form an encrypted identifier by merging the identifier with the selected true random number from the one-time pad according to a merging function; (e) sending the encrypted identifier to the second electronic device; (f) receiving the encrypted identifier by the second electronic device; (g) decrypting the encrypted identifier by performing the inverse function on the encrypted identifier to obtain the identifier; and (h) determining access to an access-controlled module according to the identifier by the second electronic device.
Preferably, the merging function includes the step of performing XOR operation with the selected true random number and the identifier. More preferably, the access-controlled module is selected from the group consisting of a physical space, an electronic device, and data. Most preferably, the physical space is selected from the group consisting of a room, a safe, an automobile, a building and a secure installation. Also most preferably, the electronic device is selected from the group consisting of a computer, an automatic money machine, a television, a cellular phone and a regular phone. Also more preferably, the data is selected from the group consisting of information related to a bank account, electronic mail (e-mail) and voice mail.
According to another embodiment of the present invention, there is provided a method for determining access by a user to an access-controlled module, the method comprising the steps of: (a) providing a first electronic device for the user and a second electronic device for the access-controlled module, each of the first and the second electronic devices having: (i) a non-volatile memory; (ii) a processor; (iii) at least one table of true random numbers being stored on the non-volatile memory, the table being identical for the first and the second electronic devices; and (iv) at least one software program for obtaining a true random number from the table, the at least one software program being stored on the non-volatile memory and the at least one software program being operated by the processor; (b) providing a communication channel for communication between the first electronic device and the second electronic device; (c) selecting a selected true random number from the table at the first and the second electronic devices according to a selection procedure, the selection procedure being identical for the first and the second electronic devices, such that the selected true random number is identical for the first and the second electronic devices; (d) encrypting an identifier by the first electronic device by merging the identifier with the selected true random number according to a merging function to form an encrypted identifier; (e) sending the encrypted identifier to the second electronic device; (f) receiving the encrypted identifier by the second electronic device; (g) decrypting the encrypted identifier by performing a reverse-function on the encrypted identifier to obtain the identifier, the reverse-function being a reverse of the merging function; and (h) determining access to the access-controlled module according to the identifier by the second electronic device.
According to yet another embodiment of the present invention, there is provided a method for secure transmission of a message, the method comprising the steps of: (a) providing a first electronic device at a first location and a second electronic device at a second location, each of the first and the second electronic devices having: (i) a non-volatile memory; (ii) a processor; (iii) at least one table of true random numbers being stored on the non-volatile memory, the table being identical for the first and the second electronic devices; and (iv) at least one software program for obtaining a true random number from the table, the at least one software program being stored on the non-volatile memory and the at least one software program being operated by the processor; (b) providing a communication channel for communication between the first electronic device and the second electronic device; (c) selecting a selected true random number from the table at the first and the second electronic devices according to a selection procedure, the selection procedure being identical for the first and the second electronic devices, such that the selected true random number is identical for the first and the second electronic devices; (d) encrypting the message by the first electronic device by merging at least a portion of the message with the selected true random number according to a merging function to form an encrypted message; and (e) sending the encrypted message to the second electronic device over the communication channel.
According to still another embodiment of the present invention, there is provided a device for generating an electronic one-time pad, comprising: (a) a non-volatile memory; (b) a processor; (c) a read-only table of true random numbers being stored on the non-volatile memory; (d) a first software program for obtaining an obtained true random number from the table, the first software program being stored on the non-volatile memory and the first software program being operated by the processor; (e) an input port for receiving at least a portion of a key; (f) a second software program for selecting a selected true random number according to the obtained true random number and a selection procedure, the selected true random number forming at least a portion of the electronic one-time pad; and (g) a read/write memory for storing the electronic one-time pad; the non-volatile memory, the processor and the input port being arranged on a single chip, and access into the chip being enabled only through the input port.
Preferably, the read/write memory is arranged on the single chip. Alternatively and preferably, the read/write memory is at a physically separate location.
Preferably, the second software program selects the selected true random number upon receipt of a command through the input port. Also preferably, the device further comprises an additional input port on the chip for receiving a reset signal, wherein the second software program selects the selected true random number until the chip receives the reset signal. Also preferably, the device further comprises (h) a generator for generating a generated true random number, the generated true random number forming a second portion of the key, the generator being located on the single chip; and (i) an output port, the output port being located on the single chip, such that the second portion of the key is transmittable through the output port.
More preferably, the generator includes a source of physical random phenomena, such that the generated true random number is generated from the source of physical random phenomena. Most preferably, the source of physical random phenomena is selected from the group consisting of a source of acoustic noise and a source of thermal noise.
Alternatively and more preferably, the generator is a pseudorandom number generator being operated by the processor according to at least one software program being stored in the non-volatile memory, the pseudorandom number generator being operated substantially continuously for an undefined period of time, such that the generated true random number is obtained from the pseudorandom number generator.
According to preferred embodiments of the present invention, the input port is capable of receiving a message, and at least one software program for encrypting the message to form an encrypted message according to the electronic one-time pad is stored on the non-volatile memory, the at least one software program being operated by the processor, the encrypted message being transmittable through the output port. Preferably, the input port is capable of receiving a message, and at least one software program for encrypting the message to form an encrypted message according to the electronic one-time pad is stored on a second non-volatile memory being located in a physically separate location from the chip, the at least one software program being operated by the processor, the encrypted message being transmittable through the output port.
According to other preferred embodiments of the present invention, the non-volatile memory contains an identifier and at least one software program for encrypting the identifier to form an encrypted identifier according to the electronic one-time pad, the at least one software program being operated by the processor, the encrypted identifier being transmittable through the output port.
According to still other preferred embodiments of the present invention, a plurality of read-only tables of random numbers is stored on the non-volatile memory, and at least one software program for selecting at least one of the tables is stored on the non-volatile memory and is operable by the processor, such that the electronic one-time pad is produced according to the at least one of the tables. More preferably, there is provided a system for secure communication, comprising: (a) a first device according to the preferred embodiments of the present invention; and (b) a second device according to the preferred embodiments of the present invention; wherein at least one of the plurality of read-only tables of random numbers is identical on the first device and on the second device, such that the software program is capable of selecting the at least one identical table.
Hereinafter, the term xe2x80x9cmessagexe2x80x9d refers to a collection of data in the form of bytes including, but not limited to, textual information and image information.
Hereinafter, the term xe2x80x9ccommunication channelxe2x80x9d refers to any connection between two electronic devices which enables communication to occur. Examples of communication channels include, but are not limited to, the regular telephony network, any computer network, both wireless cable and cable transmitted by wire, and the cellular phone network. Under certain circumstances, these communication channels may also be considered xe2x80x9cinsecure channelsxe2x80x9d, by which it is meant that these types of communication channels are potentially, although not necessarily, susceptible to interception of transmitted data by an unauthorized third party. Hereinafter, the term xe2x80x9copen channelxe2x80x9d refers to a channel upon which no security measures have been imposed. Similarly, the term xe2x80x9copen textxe2x80x9d refers to text transmitted over any communication channel which has not been encrypted in any way.
Examples of electronic devices include, but are not limited to, facsimile machines, telephones, cellular telephones, televisions, any other type of device intended for communication by voice, satellite dishes, television transmitters, cable head-ends and computers. Hereinafter, the term xe2x80x9ccomputer networkxe2x80x9d refers to a connection between any two computers which permits the transmission of data. Hereinafter, the term xe2x80x9ccomputerxe2x80x9d includes, but is not limited to, personal computers (PC) having an operating system such as DOS, Windows(trademark), OS/2(trademark) or Linux; Mackintosh(trademark) computers; computers having JAVA(trademark)-OS as the operating system; and graphical workstations such as the computers of Sun Microsystems(trademark) and Silicon Graphics(trademark), and other computers having some version of the UNIX operating system such as AIX or SOLARIS(trademark) of Sun Microsystems(trademark); or any other known and available operating system. Hereinafter, the term xe2x80x9cWindows(trademark)xe2x80x9d includes but is not limited to Windows95(trademark), Windows 3.x(trademark) in which xe2x80x9cxxe2x80x9d is an integer such as xe2x80x9c1xe2x80x9d, Windows NT(trademark), Windows98(trademark), Windows CE(trademark) and any upgraded versions of these operating systems by Microsoft Inc. (Seattle, Wash., USA).
Hereinafter, the term xe2x80x9cnon-secure communication devicexe2x80x9d refers to any device which is not capable of performing the method of secure communication of the present invention. Similarly, the term xe2x80x9cnon-secure communication protocolxe2x80x9d refers to any protocol other than the secure communication protocol of the present invention. As such, the term xe2x80x9cnon-securexe2x80x9d is not intended to indicate the actual security quality or characteristics of the non-secure device or of the non-secure protocol, but only to indicate that the device or protocol is not of the present invention.
Hereinafter, the term xe2x80x9ctrue random numberxe2x80x9d refers to a number which is stochastically random, in the sense that it is not capable of being repeatedly regenerated at will. The term xe2x80x9cpseudorandom numberxe2x80x9d refers to a number which is produced according to a mathematical algorithm and which can theoretically be repeatedly regenerated. The term xe2x80x9cpseudorandom number generatorxe2x80x9d refers to a mathematical algorithm according to which a computer is able to generate a pseudorandom number. One characteristic of such a pseudorandom number generator is that the seed is automatically changed every time a pseudorandom number is generated. Hereinafter, the term xe2x80x9cselection procedurexe2x80x9d refers to both choosing an existing true random number from a table of true random numbers, for example, and to a procedure in which such an existing true random number is further changed, altered or manipulated.
Hereinafter, the term xe2x80x9cautomatic money machinexe2x80x9d refers to a machine from which cash may be obtained upon inserting a card with a magnetic strip and entering an identification number such as a PIN (personal identification number).